package class10;

import class10.TreeTools.*;
import java.util.Stack;

/**
 * <a href="https://leetcode.cn/problems/binary-tree-preorder-traversal/">144. 二叉树的前序遍历</a>
 * <a href="https://leetcode.cn/problems/binary-tree-inorder-traversal/">94. 二叉树的中序遍历</a>
 * <a href="https://leetcode.cn/problems/binary-tree-postorder-traversal/">145. 二叉树的后序遍历</a>
 */
public class Code03_UnRecursiveTraversalBT {

    // 非递归先序遍历
    public static void pre(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            root = stack.pop();
            System.out.printf("%d ", root.value);
            if (root.right != null) {
                stack.push(root.right);
            }
            if (root.left != null) {
                stack.push(root.left);
            }
        }
    }

    // 非递归中序遍历
    public static void in(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return;
        }
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                System.out.printf("%d ", root.value);
                root = root.right;
            }
        }
    }

    // 非递归后序遍历
    public static void pos(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> result = new Stack<>();
        if (root == null) {
            return;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            root = stack.pop();
            result.push(root);
            if (root.left != null) {
                stack.push(root.left);
            }
            if (root.right != null) {
                stack.push(root.right);
            }
        }
        while (!result.isEmpty()) {
            System.out.printf("%d ", result.pop().value);
        }
    }

    public static void main(String[] args) {
        TreeNode treeNode = TreeTools.stringToTreeNode("[1,2,3,4,5,6,7,8]");
        pre(treeNode);
        System.out.println();
        in(treeNode);
        System.out.println();
        pos(treeNode);
    }

}
